Public HeadNode As BinaryTreeItem

'插入结点

Sub InsertNode(bstTree As BinaryTreeItem, newNode As BinaryTreeItem)
    
    Dim pTree As BinaryTreeItem
    
    Dim qTree As BinaryTreeItem
    
    Set qTree = Nothing
    
    If bstTree Is Nothing Then
        
        Set bstTree = newNode
        
        Exit Sub
        
    End If
    
    Set pTree = bstTree
    
    Do While (Not pTree Is Nothing)
        
        If pTree.Value <> newNode.Value Then
            
            Set qTree = pTree
            
            If pTree.Value > newNode.Value Then
                
                Set pTree = pTree.LeftChild
                
            Else
                
                Set pTree = pTree.RightChild
                
            End If
            
        End If
        
    Loop
    
    If pTree Is Nothing Then
        
        If qTree.Value > newNode.Value Then
            
            Set qTree.LeftChild = newNode
            
        Else
            
            Set qTree.RightChild = newNode
            
        End If
        
    End If
    
End Sub

'创建排序二叉树

Function CreateBinarySortTree(arr() As BinaryTreeItem) As BinaryTreeItem
    
    Dim bst As BinaryTreeItem, pst As BinaryTreeItem
    
    Dim i As Integer
    
    Dim length As Integer
    
    length = UBound(arr) - LBound(arr) + 1
    
    Set bst = Nothing
    
    For i = 0 To length - 1
        
        Set pst = New BinaryTreeItem
        
        pst.Value = arr(i).Value
        
        Set pst.LeftChild = Nothing
        
        Set pst.RightChild = Nothing
        
        Call InsertNode(bst, pst)
        
    Next i
    
    Set HeadNode = bst
    
    Set CreateBinarySortTree = bst
    
End Function

'遍历二叉树

Public Sub WalkInorder()
    
    Call InOrder(HeadNode)
    
End Sub

'中序遍历

Private Sub InOrder(bstNode As BinaryTreeItem)
    
    If Not bstNode Is Nothing Then
        
        Call InOrder(bstNode.LeftChild)
        
        Debug.Print bstNode.Value
        
        Call InOrder(bstNode.RightChild)
        
    End If
    
End Sub
